Algoritmo QR

El algoritmo QR es un algoritmo usado en álgebra lineal para el cálculo de valores y vectores propios de una matriz.

Se basa en la descomposición QR, desarrollada en la década de 1950 por John G.F. Francis (Reino Unido) y Vera N. Kublánovskaya (URSS), de forma independiente.​ Esto es, usa la oportunidad de representar cualquier matriz regular H en forma de producto de $H=QR$ de una matriz ortogonal Q por una matriz triangular superior R.​ La idea básica es usar dicha descomposición para reescribir la matriz como el producto de una matriz ortogonal y una matriz triangular superior. Si se multiplica a la inversa, la matriz resultante sigue teniendo los mismos valores propios e iterando se puede llegar a una matriz que los contenga en la diagonal.

Descripción del algoritmo

Formalmente, sea A una matriz real de la que queremos calcular los valores propios, se asigna A₀:=A. En adelante se calculan las siguientes iteraciones de forma:

• A_k=Q_kR_k dondeQ_k es una matriz ortogonal y R_k es una matriz triangular superior.
• A_k+1 = R_kQ_k. Se ha de notar que

$A_{k+1}=R_{k}Q_{k}=Q_{k}^{T}Q_{k}R_{k}Q_{k}=Q_{k}^{T}A_{k}Q_{k}=Q_{k}^{-1}A_{k}Q_{k},$

luego todas las A_k son matrices semejantes y por tanto tienen los mismos valores propios. El algoritmo es numéricamente estable porque opera por transformaciones ortogonales.

Bajo ciertas condiciones​ las matrices A_k convergen a una matriz triangular que es la triangulación de Schur de A. Dado que los valores propios de una matriz triangular están listados en su diagonal, se pueden obtener directamente entonces. Comprobar su convergencia es impráctico, pero se puede acotar el error por el Teorema de Gerschgorin.

Interpretación

El algoritmo QR se puede considerar una versión más sofisticada del método de las potencias. Ambos métodos multiplican repetidamente un vector por la matriz de la que se quieren conocer los valores propios, normalizando después de cada iteración. Así este converge a los valores deseados.

Sin embargo, mientras que el método de las potencias solo proporciona el mayor de los valores propios, el método QR usa la descomposición homónima para normalizar y ortogonalizar tras cada iteración. Así para el valor final cuando converge AQ=QΛ se obtiene la matriz diagonal Λ que contiene todos los valores propios y por tanto Q queda con los vectores propios en las columnas.

Variantes del algoritmo

Reducción del coste computacional

En la forma más simple, este algoritmo es muy costoso computacionalmente. Se puede mitigar esto convirtiendo A en una matriz de Hessenberg, lo que ocupa ${\begin{matrix}{\frac {10}{3}}\end{matrix}}n^{3}+O(n^{2})$ operaciones aritméticas usando la transformación de Householder​​ Determinar la descomposición QR de una matriz de Hessenberg lleva $6n^{2}+O(n)$ operaciones. Sin embargo, la matriz de Hessenberg es casi triangular, por lo que su uso como punto de partida reduce el número de iteraciones para que el algoritmo converja.

Si la matriz original es una matriz simétrica, la matriz de Hessenberg es también simétrica y por tanto tridiagonal. Como ella, lo serán todas las A_k. Entonces el proceso ocupa ${\begin{matrix}{\frac {4}{3}}\end{matrix}}n^{3}+O(n^{2})$ operaciones, usando una técnica basada en la reducción de Householder.​​ Determinar la descomposición QR de una matriz simétrica tridiagonal cuesta $O(n)$ operaciones.​

Otras variantes

Una variante del algoritmo QR es el algoritmo Golub-Kahan-Reinsch, que empieza reduciendo una matriz a bidiagonal.​ Dicha variante fue descrita por primera vez por Golub y Kahan (1965).

La subrutina LAPACK de DBDSQR implementa este método iterativo con algunas modificaciones para cubrir el caso de que los valores sean demasiado pequeños (Demmel y Kahan, 1990). Junto a un primer paso usando reflexiones de Householder y, si procede, la descomposición QR, esto forma la rutina DGESVD para el cálculo de la descomposición en valores singulares.

Historia

El algoritmo QR fue precedido por el algoritmo LR, que se apoya en la descomposición LU. El algoritmo QR es en comparación más estable así que le desplazó y el LR es poco usado hoy en día. Sin embargo, fue el primer paso hacia las técnicas actuales QR.

El algoritmo LR fue desarrollado en los comienzos de la década de 1950 por Heinz Rutishauer, que trabajaba como asistente de Eduard Stiefel en la Escuela Politécnica Federal de Zúrich. Stiefel sugirió que Rutishauer usara la secuencia de momentos y₀^T A^k x₀, k = 0, 1, … (donde x₀ e y₀ son vectores arbitrarios) para encontrar los valores propios de A. Rutishauer usó un algoritmo de Alexander Aitken para esta tarea y lo desarrolló en un algoritmo de cociente-diferencia (quotient–difference algorithm), de donde deriva el término algoritmo qd.

Tras formularlo de una forma apropiada computacionalmente, descubrió que el algoritmo era en realidad la iteración A_k = L_kU_k (Descomposición LU), A_k+1 = U_kL_k, aplicado sobre una matriz tridiagonal de la que deriva el algoritmo LR.​

Enlaces externos

• Eigenvalue problem en PlanetMath.
• Prof. Peter Olver's notes on orthogonal bases and the workings of the QR algorithm
• Module for the QR Method

• Datos: Q453132